﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution239
    {
        public int[] MaxSlidingWindow(int[] nums, int k)
        {
            //Queue<int> q = new Queue<int>();
            LinkedList<int> queue   = new LinkedList<int>();
            int len=nums.Length;
           IList<int> res = new List<int>();  
            for(int i = 0; i < k; i++)
            {
                while (queue.Count>0||nums[i] >= nums[queue.Last()])
                {
                    queue.RemoveLast();

                   
                }
                queue.AddLast(i);
            }

            res.Add(nums[queue.First()]);
            for (int i = k; i <len; i++)
            {

                while (queue.Count > 0 || nums[i] >= nums[queue.Last()])
                {
                    queue.RemoveLast();


                }
                queue.AddLast(i);
                while (queue.First()<=i-k)
                {
                    queue.RemoveFirst();
                }

                res.Add(nums[queue.First()]);
            }

            return res.ToArray();
        }
    }
}
